package BackTracking.subset;//给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
//
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0]
//输出：[[],[0]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10 
// -10 <= nums[i] <= 10 
// nums 中的所有元素 互不相同 
// 
// Related Topics 位运算 数组 回溯 👍 1388 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class subsets {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        /**
         * 组合和分割问题是在N叉树中，收集叶子节点，可以剪枝优化
         * 子集问题是收集所有节点，不用剪枝
         * */
        if(nums.length==0){
            res.add(path);
            return res;
        }
        sub(nums,0, nums.length);
        return res;
    }

    private void sub(int[] nums, int start, int n){

        //进来就收集
        res.add(new ArrayList<>(path));
        //当到达叶子时，返回
        if(start >= n){
            return;
        }
        for (int i = start; i < n; i++) {
            path.add(nums[i]);
            sub(nums, i+1, n);
            path.remove(path.size()-1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
